// 42.接雨水
package Leetcode_Second_Brush;

public class Solution042 {
    public int trap(int[] height) {
        int[] leftHeight = new int[height.length];
        int[] rightHeight = new int[height.length];

        leftHeight[0] = 0;
        for (int i = 1; i < height.length; i++) {
            leftHeight[i] = Math.max(leftHeight[i - 1], height[i - 1]);
        }

        rightHeight[height.length - 1] = 0;
        for (int i = height.length - 2; i >= 0; i--) {
            rightHeight[i] = Math.max(rightHeight[i + 1], height[i + 1]);
        }

        int result = 0;
        for (int i = 0; i < height.length; i++) {
            if (Math.min(leftHeight[i], rightHeight[i]) > height[i])
                result += Math.min(leftHeight[i], rightHeight[i]) - height[i];
        }

        return result;
    }
}
